home *** CD-ROM | disk | FTP | other *** search
- /*
- * Last Hacked by Johan Widen, jw@sics.se, 17 Jan 88.
- * Decreased memory use by cleaning up the data types. "new style" context
- * diffs. File dates are now displayed under UNIX and Amiga-DOS.
- * Incorporated documentation cleanup and TURBO-C adaptions by mike2@lcuxa.
- *
- * Previously Hacked by Robert A. Larson, blarson@ecla.usc.edu, Nov 29 86
- * OSK support.
- * Real context diffs, with a couple of minor problems:
- * If the first change is deleting leading lines, and the second
- * such that the context overlaps the deleted lines, the deleted
- * lines are output as context. This is consistant with other
- * cases of overlapping context, but patch doesn't like it. It's
- * not hard to manually fix the diff in this (rare?) case.
- * At most 9 lines of context is output.
- *
- * Previously Hacked by John Gilmore, hoptoad!gnu, 26Sep86.
- * Compiles and runs under Unix. Much faster since it doesn't reallocate
- * every data structure in the inner loop(!). Compatible with Unix diff
- * output format, though it occasionally finds different sets of changed
- * lines (both are valid). -c option needs work. Also, ftell's in
- * <check> should be dumped when possible.
- *
- From: EVERHART%ARISIA%rca.com@CSNET-RELAY.ARPA
- Message-Id: <8608201845.AA15181@lll-crg.ARPA>
- Date: Wed, 20 Aug 86 10:34 EDT
- To: hoptoad!gnu@LLL-CRG.ARPA
- Subject: Decus C DIFF source.
- */
-
- /*
- * D I F F
- */
-
- /* For VMS:
- )BUILD $(TKBOPTIONS) = {
- TASK = ...DIF
- }
- */
-
- /*
- * OSK changes: since OSK doesn't have realloc, put the size
- * allocated in the head of each allocated region. This code
- * assumes int is a maximally alligned type.
- */
-
- /*
- * Borland Turbo C instructions.
- *
- * 1. Make certain that TURBO is #defined.
- * 2. Compile in the Large model.
- * 3. Set the optimizations:
- * a) to optimize for speed, not size
- * b) to use register variables
- * c) to invoke register optimization
- * c) to invoke jump optimization
- */
-
-
- #ifdef TURBO
- #include <alloc.h>
- #include <errno.h>
- #include <process.h>
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #else
- #include <stdio.h>
- #include <ctype.h>
- #endif
-
- #ifdef unix
- #include <sys/types.h>
- #include <sys/stat.h>
- #endif
-
- #ifdef vms
- #include <ssdef.h>
- #include <stsdef.h>
- #define IO_SUCCESS (SS | STS)
- #define IO_ERROR SS
- #endif
-
- #ifdef AMIGA
- #ifndef MANX
- #ifndef LATTICE
- #define LATTICE 1
- #define ANSI 1
- #endif
- #endif
- #ifdef LATTICE
- #include <stdlib.h>
- #include <string.h>
-
- extern char *_TZ;
- #endif
- #endif
- /*
- * Note: IO_SUCCESS and IO_ERROR are defined in the Decus C stdio.h file
- */
- #ifndef IO_SUCCESS
- #define IO_SUCCESS 0
- #endif
- #ifndef IO_ERROR
- #define IO_ERROR 1
- #endif
-
- #define EOS 0
- #ifdef unix
- char temfile[L_tmpnam];
- char *tmpnam();
- #define TEMPFILE (temfile[0]? temfile: tmpnam(temfile))
- #else
- #define TEMPFILE "diff.tmp"
- #endif
- #define TRUE 1
- #define FALSE 0
-
- #ifdef pdp11
- #define short int
- #endif
-
- typedef short LINENO;
- typedef unsigned short HASH;
-
- typedef struct candidate {
- LINENO b; /* Line in fileB */
- LINENO a; /* Line in fileA */
- LINENO link; /* Previous candidate */
- } CANDIDATE;
-
- typedef struct line {
- HASH hash; /* Hash value etc. */
- LINENO serial; /* Line number */
- } LINE;
-
- #define MAXLINES 32760 /* depends on sizeof(short) */
- #define LSIZE_INC 200 /* # of line entries to alloc at once */
-
- LINE *file[2]; /* Hash/line for total file */
- #define fileA file[0]
- #define fileB file[1]
-
- LINE *sfile[2]; /* Hash/line after prefix */
- #define sfileA sfile[0]
- #define sfileB sfile[1]
-
- int len[2]; /* Actual lines in each file */
- #define lenA len[0]
- #define lenB len[1]
-
- int slen[2]; /* Squished lengths */
- #define slenA slen[0]
- #define slenB slen[1]
-
- int prefix; /* Identical lines at start */
- int suffix; /* Identical lines at end */
-
- FILE *infd[2] = { NULL, NULL }; /* Input file identifiers */
- FILE *tempfd; /* Temp for input redirection */
-
- #ifndef LATTICE
- extern long ftell();
- extern FILE *fopen();
- #ifdef TURBO
- extern void *malloc();
- #else
- extern char *malloc();
- #endif
- #endif
-
- #ifdef ANSI
- int error(char *,);
- char *fgetss(char *, int, FILE *);
- HASH hash(char *);
- HASH newcand(LINENO, LINENO, LINENO);
- unsigned search(unsigned, unsigned, LINENO);
- unsigned subseq();
- #else
- char *fgetss();
- HASH hash();
- HASH newcand();
- unsigned search();
- unsigned subseq();
- #endif
- /*
- * The following vectors overlay the area defined by fileA
- */
-
- HASH *class; /* Unsorted line numbers */
- HASH *klist; /* Index of element in clist */
- CANDIDATE *clist; /* Storage pool for candidates */
- int clength = 0; /* Number of active candidates */
- #define CSIZE_INC 50 /* How many to allocate each time we have to */
- int csize = CSIZE_INC; /* Current size of storage pool */
-
- LINENO *match; /* Longest subsequence */
- long *oldseek; /* Seek position in file A */
-
- /*
- * The following vectors overlay the area defined by fileB
- */
-
- LINENO *member; /* Concatenated equiv. classes */
- long *newseek; /* Seek position in file B */
- char *textb; /* Input from file2 for check */
-
- /*
- * Global variables
- */
-
- int eflag = FALSE; /* Edit script requested */
- int bflag = FALSE; /* Blank supress requested */
- int cflag = FALSE; /* Context printout */
- int iflag = FALSE; /* Ignore case requested */
- char text[257]; /* Input line from file1 */
- extern char *myalloc(); /* Storage allocator */
-
- extern char *compact(); /* Storage compactor */
-
- #ifdef DEBUG
- #ifndef OSK
- #define TIMING
- #endif
- #endif
- #ifdef TIMING
- extern long time();
- extern char *358mend;
- long totaltime;
- long sectiontime;
- char *mstart;
- #endif
-
- main(argc, argv)
- int argc;
- char **argv;
- /*
- * Diff main program
- */
- {
- register int i;
- register char *ap;
-
- #ifdef OSK
- extern int _memmins;
- _memmins = 16 * 1024; /* tell OSK we will malloc a lot */
- #endif
- #ifdef TIMING
- sectiontime = time(&totaltime);
- #endif
- #ifdef vms
- argc = getredirection(argc,argv);
- #endif
- while (argc > 1 && *(ap = argv[1]) == '-' && *++ap != EOS) {
- while (*ap != EOS) {
- switch ((*ap++)) {
- case 'b':
- bflag++;
- break;
-
- case 'c':
- if (*ap > '0' && *ap <= '9') cflag = *ap++ - '0';
- else cflag = 3;
- break;
-
- case 'e':
- eflag++;
- break;
-
- case 'i':
- iflag++;
- break;
-
- default:
- fprintf(stderr,
- "Warning, bad option '%c'\n",
- ap[-1]);
- break;
- }
- }
- argc--;
- argv++;
- }
-
- if (argc != 3)
- error("Usage: diff [-options] file1 file2");
- if (cflag && eflag) {
- fprintf(stderr,
- "Warning, -c and -e are incompatible, -c supressed.\n");
- cflag = FALSE;
- }
- argv++;
- for (i = 0; i <= 1; i++) {
- if (argv[i][0] == '-' && argv[i][1] == EOS) {
- infd[i] = stdin;
- if ((tempfd = fopen(TEMPFILE, "w")) == NULL)
- cant(TEMPFILE, "work", 1);
- }
- else {
- infd[i] = fopen(argv[i], "r");
- if (!infd[i]) cant(argv[i], "input", 2); /* Fatal error */
- }
- }
-
- if (infd[0] == stdin && infd[1] == stdin)
- error("Can't diff two things both on standard input.");
-
- if (infd[0] == NULL && infd[1] == NULL) {
- cant(argv[0], "input", 0);
- cant(argv[1], "input", 1);
- }
- #ifdef vms
- else if (infd[1] == NULL)
- opendir(1, &argv[1], infd[0]);
- else if (infd[0] == NULL)
- opendir(0, &argv[0], infd[1]);
- #endif
-
- /*
- * Read input, building hash tables.
- */
- input(0);
- input(1);
- if(lenA > MAXLINES || lenB > MAXLINES)
- error("Can't handle files with more than %d lines.", MAXLINES);
- squish();
- #ifdef DEBUG
- printf("before sort\n");
- for (i = 1; i <= slenA; i++)
- printf("sfileA[%d] = %6d %06o\n",
- i, sfileA[i].serial, sfileA[i].hash);
- for (i = 1; i <= slenB; i++)
- printf("sfileB[%d] = %6d %06o\n",
- i, sfileB[i].serial, sfileB[i].hash);
- #endif
- sort(sfileA, slenA);
- sort(sfileB, slenB);
- #ifdef TIMING
- ptime("input");
- #endif
- #ifdef DEBUG
- printf("after sort\n");
- for (i = 1; i <= slenA; i++)
- printf("sfileA[%d] = %6d %06o\n",
- i, sfileA[i].serial, sfileB[i].hash);
- for (i = 1; i <= slenB; i++)
- printf("sfileB[%d] = %6d %06o\n",
- i, sfileB[i].serial, sfileB[i].hash);
- #endif
- /*
- * Build equivalence classes.
- */
- member = (LINENO *)fileB;
- equiv(); /* This will overwrite fileB */
- member = (LINENO *)compact((char *)member, (slenB + 2) * sizeof (LINENO),
- "squeezing member vector");
- /* sfileB and fileB are no longer valid */
- /*
- * Reorder equivalence classes into array class[]
- */
- class = (HASH *)fileA;
- unsort(); /* This will overwrite fileA */
- class = (HASH *)compact((char *)class, (slenA + 2) * sizeof (HASH),
- "compacting class vector");
- /* sfileA and fileA are no longer valid */
- #ifdef TIMING
- ptime("equiv/unsort");
- #endif
- /*
- * Find longest subsequences
- */
- klist = (HASH *)myalloc((slenA + 2) * sizeof (HASH), "klist");
- clist = (CANDIDATE *)myalloc(csize * sizeof (CANDIDATE), "clist");
- i = subseq();
- #ifndef OSK
- free((char *)member);
- free((char *)class);
- #else
- free((char *)member - sizeof(int));
- free((char *)class - sizeof(int));
- #endif
- match = (LINENO *)myalloc((lenA + 2) * sizeof (LINENO), "match");
- unravel(klist[i]);
- #ifndef OSK
- free((char *)clist);
- free((char *)klist);
- #else
- free((char *)clist - sizeof(int));
- free((char *)klist - sizeof(int));
- #endif
- #ifdef TIMING
- ptime("subsequence/unravel");
- #endif
- /*
- * Check for fortuitous matches and output differences
- */
- oldseek = (long *)myalloc((lenA + 2) * sizeof (* oldseek), "oldseek");
- newseek = (long *)myalloc((lenB + 2) * sizeof (* newseek), "newseek");
- textb = myalloc(sizeof text, "textbuffer");
- check(argv[0], argv[1]);
- #ifdef TIMING
- ptime("check");
- #endif
- output(argv[0], argv[1]);
- #ifdef TIMING
- ptime("output");
- printf("%ld seconds required\n", sectiontime - totaltime);
- #endif
- if (tempfd != NULL) {
- fclose(tempfd);
- #ifdef vms
- remove(TEMPFILE);
- #else
- unlink(TEMPFILE);
- #endif
- }
- }
-
-
- input(which)
- int which; /* 0 or 1 to redefine infd[] */
- /*
- * Read the file, building hash table
- */
- {
- register LINE *lentry;
- register int linect = 0;
- FILE *fd;
- int lsize = LSIZE_INC;
-
- lentry = (LINE *)myalloc(sizeof(LINE) * (lsize+3), "line");
- fd = infd[which];
- while (!getline(fd, text)) {
- if (++linect >= lsize) {
- lsize += LSIZE_INC;
- lentry = (LINE *)compact((char *)lentry,
- (lsize + 3) * sizeof(LINE),
- "extending line vector");
- }
- lentry[linect].hash = hash(text);
- }
- /*
- * If input was from stdin ("-" command), finish off the temp file.
- */
- if (fd == stdin) {
- fclose(tempfd);
- tempfd = infd[which] = fopen(TEMPFILE, "r");
- }
- /* If we wanted to be stingy with memory, we could realloc lentry down
- * to its exact size (+3 for some odd reason) here. No need? */
- len[which] = linect;
- file[which] = lentry;
- }
-
- squish()
- /*
- * Look for initial and trailing sequences that have identical hash values.
- * Don't bother building them into the candidate vector.
- */
- {
- register int i;
- register LINE *ap;
- register LINE *bp;
- int j;
- int k;
-
- /*
- * prefix -> first line (from start) that doesn't hash identically
- */
- i = 0; ap = &fileA[1]; bp = &fileB[1];
- while (i < lenA && i < lenB && ap->hash == bp->hash) {
- i++; ap++; bp++;
- }
- prefix = i;
- /*
- * suffix -> first line (from end) that doesn't hash identically
- */
- j = lenA - i;
- k = lenB - i;
- ap = &fileA[lenA];
- bp = &fileB[lenB];
- i = 0;
- while (i < j && i < k && ap->hash == bp->hash) {
- i++; ap--; bp--;
- }
- suffix = i;
- /*
- * Tuck the counts away
- */
- for (k = 0; k <= 1; k++) {
- sfile[k] = file[k] + prefix;
- slen[k] = len[k] - prefix - suffix;
-
- for (i = 0, ap = sfile[k]; i <= slen[k]; i++, ap++) {
- ap->serial = i;
- }
- }
- }
-
- sort(vector, vecsize)
- LINE *vector; /* What to sort */
- int vecsize; /* How many to sort */
- /*
- * Sort hash entries
- */
- {
- register int j;
- register LINE *aim;
- register LINE *ai;
- int mid;
- int k;
- LINE work;
-
- for (j = 1; j <= vecsize; j *= 2);
- mid = (j - 1);
- while ((mid /= 2) != 0) {
- k = vecsize - mid;
- for (j = 1; j <= k; j++) {
- for (ai = &vector[j]; ai > vector; ai -= mid) {
- aim = &ai[mid];
- if (aim->hash > ai->hash ||
- aim->hash == ai->hash &&
- aim->serial > ai->serial)
- break;
- work.hash = ai->hash;
- ai->hash = aim->hash;
- aim->hash = work.hash;
- work.serial = ai->serial;
- ai->serial = aim->serial;
- aim->serial = work.serial;
- }
- }
- }
- }
-
- equiv()
- /*
- * Build equivalence class vector
- */
- {
- register LINE *ap;
- register LINE *bp;
- register LINENO *mp;
- register int j;
- LINE *atop, *btop;
-
- #ifdef DEBUG
- printf("equiv entry\n");
- for (j = 1; j <= slenA; j++)
- printf("sfileA[%d] = %6d %06o\n",
- j, sfileA[j].serial, sfileA[j].hash);
- for (j = 1; j <= slenB; j++)
- printf("sfileB[%d] = %6d %06o\n",
- j, sfileB[j].serial, sfileB[j].hash);
- #endif
- j = 1;
- ap = &sfileA[1];
- bp = &sfileB[1];
- atop = &sfileA[slenA];
- while (ap <= atop && j <= slenB) {
- if (ap->hash < bp->hash) {
- ap->hash = 0;
- ap++;
- }
- else if (ap->hash == bp->hash) {
- ap->hash = j;
- ap++;
- }
- else {
- bp++;
- j++;
- }
- }
- while (ap <= atop) {
- ap->hash = 0;
- ap++;
- }
- sfileB[slenB + 1].hash = 0;
- #ifdef DEBUG
- printf("equiv exit\n");
- for (j = 1; j <= slenA; j++)
- printf("sfileA[%d] = %6d %06o\n",
- j, sfileA[j].serial, sfileA[j].hash);
- for (j = 1; j <= slenB; j++)
- printf("sfileB[%d] = %6d %06o\n",
- j, sfileB[j].serial, sfileB[j].hash);
- #endif
- bp = sfileB;
- btop = &sfileB[slenB];
- mp = member;
- while (++bp <= btop) {
- *(++mp) = -(bp->serial);
- while (bp[1].hash == bp->hash) {
- bp++;
- *(++mp) = bp->serial;
- }
- }
- *(++mp) = -1;
- #ifdef DEBUG
- for (j = 0; j <= slenB; j++)
- printf("member[%d] = %d\n", j, member[j]);
- #endif
- }
-
- unsort()
- /*
- * Build class vector
- */
- {
- HASH *temp;
- register HASH *tp;
- register LINE *ap;
- register HASH *cp;
- LINE *evec;
- HASH *eclass;
- #ifdef DEBUG
- int i;
- #endif
-
- tp = temp = (HASH *)myalloc((slenA + 1) * sizeof(HASH), "unsort scratch");
- ap = &sfileA[1];
- evec = &sfileA[slenA];
- while (ap <= evec) {
- #ifdef DEBUG
- printf("temp[%2d] := %06o\n", ap->serial, ap->hash);
- #endif
- tp[ap->serial] = ap->hash;
- ap++;
- }
- /*
- * Copy into class vector and free work space
- */
- cp = &class[1];
- eclass = &class[slenA];
- tp = &temp[1];
- while (cp <= eclass)
- *cp++ = *tp++;
- #ifndef OSK
- free((char *) temp);
- #else
- free((char *)temp - sizeof(int));
- #endif
- #ifdef DEBUG
- printf("unsort exit\n");
- for (i = 1; i <= slenA; i++)
- printf("class[%d] = %d %06o\n", i, class[i], class[i]);
- #endif
- }
-
- unsigned
- subseq()
- /*
- * Generate maximum common subsequence chain in clist[]
- */
- {
- int a;
- register unsigned ktop;
- register LINENO b;
- register unsigned s;
- unsigned r;
- HASH i;
- HASH cand;
-
- klist[0] = newcand(0, 0, -1);
- klist[1] = newcand((LINENO) (slenA + 1), (LINENO) (slenB + 1), -1);
- ktop = 1; /* -> guard entry */
- for (a = 1; a <= slenA; a++) {
- /*
- * For each non-zero element in fileA ...
- */
- if ((i = class[a]) == 0)
- continue;
- cand = klist[0]; /* No candidate now */
- r = 0; /* Current r-candidate */
- do {
- #ifdef DEBUG
- printf("a = %d, i = %d, b = %d\n", a, i, member[i]);
- #endif
- /*
- * Perform the merge algorithm
- */
- if ((b = member[i]) < 0)
- b = -b;
- #ifdef DEBUG
- printf("search(%d, %d, %d) -> %d\n",
- r, ktop, b, search(r, ktop, b));
- #endif
- if (s = search(r, ktop, b)) {
- if (clist[klist[s]].b > b) {
- klist[r] = cand;
- r = s;
- cand = newcand((LINENO) a, b, klist[s-1]);
- #ifdef DEBUG
- dumpklist(ktop, "klist[s-1]->b > b");
- #endif
- }
- if (s >= ktop) {
- klist[ktop + 1] = klist[ktop];
- ktop++;
- #ifdef DEBUG
- klist[r] = cand;
- dumpklist(ktop, "extend");
- #endif
- break;
- }
- }
- } while (member[++i] > 0);
- klist[r] = cand;
- }
- #ifdef DEBUG
- printf("last entry = %d\n", ktop - 1);
- #endif
- return(ktop - 1); /* Last entry found */
- }
-
- HASH
- newcand(a, b, pred)
- LINENO a; /* Line in fileA */
- LINENO b; /* Line in fileB */
- LINENO pred; /* Link to predecessor, index in cand[] */
- {
- register CANDIDATE *new;
-
- clength++;
- if (++clength >= csize) {
- csize += CSIZE_INC;
- clist = (CANDIDATE *)compact((char *)clist,
- csize * sizeof (CANDIDATE),
- "extending clist");
- }
- new = &clist[clength - 1];
- new->a = a;
- new->b = b;
- new->link = pred;
- return((HASH) (clength - 1));
- }
-
- unsigned
- search(low, high, b)
- register unsigned low;
- register unsigned high;
- register LINENO b;
- /*
- * Search klist[low..top] (inclusive) for b. If klist[low]->b >= b,
- * return zero. Else return s such that klist[s-1]->b < b and
- * klist[s]->b >= b. Note that the algorithm presupposes the two
- * preset "fence" elements, (0, 0) and (slenA, slenB).
- */
- {
- register LINENO temp;
- register unsigned mid;
-
- if (clist[klist[low]].b >= b)
- return(0);
- while ((mid = (low + high) / 2) > low) {
- if ((temp = clist[klist[mid]].b) > b)
- high = mid;
- else if (temp < b)
- low = mid;
- else {
- return(mid);
- }
- }
- return(mid + 1);
- }
-
-
- unravel(k)
- register int k;
- {
- register int i;
- register CANDIDATE *cp;
- int first_trailer;
- int difference;
-
- first_trailer = lenA - suffix;
- difference = lenB - lenA;
- #ifdef DEBUG
- printf("first trailer = %d, difference = %d\n",
- first_trailer, difference);
- #endif
- for (i = 0; i <= lenA; i++) {
- match[i] = (i <= prefix) ? i
- : (i > first_trailer) ? i + difference
- : 0;
- }
- #ifdef DEBUG
- printf("unravel\n");
- #endif
- while (k != -1) {
- cp = &clist[k];
- #ifdef DEBUG
- if (k < 0 || k >= clength)
- error("Illegal link -> %d", k);
- printf("match[%d] := %d\n", cp->a + prefix, cp->b + prefix);
- #endif
- match[cp->a + prefix] = cp->b + prefix;
- k = cp->link;
- }
- }
-
-
- /*
- * Check for hash matches (jackpots) and collect random access indices to
- * the two files.
- *
- * It should be possible to avoid doing most of the ftell's by noticing
- * that we are not doing a context diff and noticing that if a line
- * compares equal to the other file, we will not ever need to know its
- * file position. FIXME.
- */
- check(fileAname, fileBname)
- char *fileAname;
- char *fileBname;
- {
- register int a; /* Current line in file A */
- register int b; /* Current line in file B */
- int jackpot;
-
- /*
- * The VAX C ftell() returns the address of the CURRENT record, not the
- * next one (as in DECUS C or, effectively, other C's). Hence, the values
- * are "off by one" in the array. OFFSET compensates for this.
- */
- #ifdef vms
- #define OFFSET (-1)
- #else
- #define OFFSET 0
- #endif
-
- b = 1;
- rewind(infd[0]);
- rewind(infd[1]);
- /*
- * See above; these would be over-written on VMS anyway.
- */
- #ifndef vms
- oldseek[0] = ftell(infd[0]);
- newseek[0] = ftell(infd[1]);
- #endif
-
- jackpot = 0;
- #ifdef DEBUG
- printf("match vector\n");
- for (a = 0; a <= lenA; a++)
- printf("match[%d] = %d\n", a, match[a]);
- #endif
- for (a = 1; a <= lenA; a++) {
- if (match[a] == 0) {
- /* Unique line in A */
- oldseek[a+OFFSET] = ftell(infd[0]);
- getline(infd[0], text);
- continue;
- }
- while (b < match[a]) {
- /* Skip over unique lines in B */
- newseek[b+OFFSET] = ftell(infd[1]);
- getline(infd[1], textb);
- b++;
- }
-
- /*
- * Compare the two, supposedly matching, lines.
- * Unless we are going to print these lines, don't bother to
- * remember where they are. We only print matching lines
- * if a context diff is happening, or if a jackpot occurs.
- */
- if (cflag) {
- oldseek[a+OFFSET] = ftell(infd[0]);
- newseek[b+OFFSET] = ftell(infd[1]);
- }
- getline(infd[0], text);
- getline(infd[1], textb);
- if (strcmp(text, textb)) {
- #ifdef DEBUG
- fprintf(stderr, "Spurious match:\n");
- fprintf(stderr, "line %d in %s, \"%s\"\n",
- a, fileAname, text);
- fprintf(stderr, "line %d in %s, \"%s\"\n",
- b, fileBname, textb);
- #endif
- match[a] = 0;
- jackpot++;
- }
-
- b++;
- }
- for (; b <= lenB; b++) {
- newseek[b+OFFSET] = ftell(infd[1]);
- getline(infd[1], textb);
- }
- /*
- * The logical converse to the code up above, for NON-VMS systems, to
- * store away an fseek() pointer at the beginning of the file. For VMS,
- * we need one at EOF...
- */
- #ifdef vms
- oldseek[lenA] = ftell(infd[0]);
- getline(infd[0],text); /* Will hit EOF... */
- newseek[lenB] = ftell(infd[1]);
- getline(infd[1],textb); /* Will hit EOF... */
- #endif
-
- return(jackpot);
- }
-
- output(fileAname, fileBname)
- char *fileAname, *fileBname;
- {
- register int astart;
- register int aend;
- int bstart;
- register int bend;
-
- rewind(infd[0]);
- rewind(infd[1]);
- match[0] = 0;
- match[lenA+1] = lenB + 1;
- if (!eflag) {
- if (cflag) {
- coutput(fileAname, fileBname);
- return;
- } else {
- /*
- * Normal printout
- */
- for (astart = 1; astart <= lenA; astart = aend + 1) {
- /*
- * New subsequence, skip over matching stuff
- */
- while (astart <= lenA &&
- match[astart] == (match[astart - 1] + 1))
- astart++;
- /*
- * Found a difference, setup range and print it
- */
- bstart = match[astart - 1] + 1;
- aend = astart - 1;
- while (aend < lenA && match[aend + 1] == 0)
- aend++;
- bend = match[aend + 1] - 1;
- match[aend] = bend;
- change(astart, aend, bstart, bend);
- }
- }
- }
- else {
- /*
- * Edit script output -- differences are output "backwards"
- * for the benefit of a line-oriented editor.
- */
- for (aend = lenA; aend >= 1; aend = astart - 1) {
- while (aend >= 1
- && match[aend] == (match[aend + 1] - 1)
- && match[aend] != 0)
- aend--;
- bend = match[aend + 1] - 1;
- astart = aend + 1;
- while (astart > 1 && match[astart - 1] == 0)
- astart--;
- bstart = match[astart - 1] + 1;
- match[astart] = bstart;
- change(astart, aend, bstart, bend);
- }
- }
- if (lenA == 0)
- change(1, 0, 1, lenB);
- }
-
-
- coutput(fileAname, fileBname)
- char *fileAname, *fileBname;
- {
- int astart;
- int aend;
- int bstart;
- int bend = 0;
- int change, ctmp, cFirst, cOld;
- int a1start, a1end, b1start, b1end, a2start, a2end, b2start, b2end;
- int astartLast, aendLast, bstartLast, bendLast;
- int low;
- int numDifferences = 0;
-
- #define CINSERTION 1
- #define CDELETION 2
- #define CCHANGE 4
- for (astart = 1; astart <= lenA; astart = aend + 1) {
- if(!(change = findentry(&astart, &aend, &bstart, &bend)))
- break;
- /* find last entry to print in this diff */
- cFirst = change;
- astartLast = astart;
- aendLast = a1end = aend;
- bstartLast = bstart;
- bendLast = b1end = bend;
- for(a1start = aendLast + 1; a1start <= lenA; a1start = a1end + 1) {
- if(!(ctmp = findentry(&a1start, &a1end, &b1start, &b1end)) ||
- ((a1start - aendLast) >= 2*cflag &&
- (b1start - bendLast) >= 2*cflag))
- break;
- change |= ctmp;
- astartLast = a1start;
- aendLast = a1end;
- bstartLast = b1start;
- bendLast = b1end;
- }
- if(!numDifferences++)
- printHeader(fileAname, fileBname);
- fputs("***************\n*** ", stdout);
- range(astart, aendLast, 0);
- fputs(" ****\n", stdout);
- if (change & (CDELETION | CCHANGE)) {
- a1start = astart; a1end = aend; b2end = bend;
- cOld = cFirst;
- low = astart - cflag;
- while (a1start < astartLast) {
- a2start = a1end + 1;
- ctmp = findentry(&a2start, &a2end, &b2start, &b2end);
- fetch(oldseek, a1start, a1end, low, a2start - 1, lenA,
- infd[0], (cOld & CDELETION) ? "- " : "! ");
- cOld = ctmp;
- low = a2start;
- a1start = a2start;
- a1end = a2end;
- }
- fetch(oldseek, astartLast, aendLast, low, aendLast + cflag, lenA,
- infd[0], (cOld & CDELETION) ? "- " : "! ");
- }
- fputs("--- ", stdout);
- range(bstart, bendLast, 1);
- fputs(" ----\n", stdout);
- if (change & (CINSERTION | CCHANGE)) {
- a2start = astart; a2end = aend;
- b1start = bstart; b1end = b2end = bend;
- cOld = cFirst;
- low = bstart - cflag;
- while (a2start < astartLast) {
- a2start = a2end + 1;
- ctmp = findentry(&a2start, &a2end, &b2start, &b2end);
- fetch(newseek, b1start, b1end, low, b2start - 1, lenB,
- infd[1], (cOld & CINSERTION) ? "+ " : "! ");
- cOld = ctmp;
- low = b2start;
- b1start = b2start;
- b1end = b2end;
- }
- fetch(newseek, bstartLast, bendLast, low, bendLast + cflag, lenB,
- infd[1], (cOld & CINSERTION) ? "+ " : "! ");
- }
- aend = aendLast;
- bend = bendLast;
- }
- if (lenA == 0 && lenB > 0) {
- numDifferences++;
- printHeader(fileAname, fileBname);
- cchange(1, 0, 1, lenB);
- }
- if (!numDifferences)
- printf("No differences encountered\n");
- }
-
-
- printHeader(fileAname, fileBname)
- char *fileAname, *fileBname;
- {
- long fileDate;
- #ifdef unix
- struct stat statbuf;
- #endif
-
- #ifdef AMIGA
- #ifdef LATTICE
- _TZ = "GMT0";
- #endif
- if(infd[0] == tempfd)
- fileDate = time(0);
- else
- fileDate = getft(fileAname);
- printf("*** %s\t%s", fileAname, ctime(&fileDate));
- if(infd[1] == tempfd)
- fileDate = time(0);
- else
- fileDate = getft(fileBname);
- printf("--- %s\t%s", fileBname, ctime(&fileDate));
- #else
- #ifdef unix
- if(infd[0] == tempfd)
- fileDate = time(0);
- else {
- fstat(fileno(infd[0]), &statbuf);
- fileDate = statbuf.st_mtime;
- }
- printf("*** %s\t%s", fileAname, ctime(&fileDate));
- if(infd[1] == tempfd)
- fileDate = time(0);
- else {
- fstat(fileno(infd[1]), &statbuf);
- fileDate = statbuf.st_mtime;
- }
- printf("--- %s\t%s", fileBname, ctime(&fileDate));
- #else
- printf("*** %s\n--- %s\n", fileAname, fileBname);
- #endif
- #endif
- }
-
-
- int
- findentry(astartp, aendp, bstartp, bendp)
- int *astartp, *aendp, *bstartp, *bendp;
- {
- int save;
- register int astart = *astartp;
- register int aend;
-
- if(astart > lenA)
- return(0);
- save = match[astart - 1];
- match[astart - 1] = *bendp;
- /* Skip over matching stuff */
- while (astart <= lenA && match[astart] == (match[astart - 1] + 1))
- astart++;
- *bstartp = match[astart - 1] + 1;
- aend = astart - 1;
- while (aend < lenA && match[aend + 1] == 0)
- aend++;
- *bendp = match[aend + 1] - 1;
- match[*astartp - 1] = save;
- *astartp = astart;
- *aendp = aend;
- if (astart > aend) {
- if (*bstartp > *bendp)
- return(0);
- else
- return(CINSERTION);
- } else if (*bstartp > *bendp)
- return(CDELETION);
- else
- return(CCHANGE);
- }
-
-
- /*
- * Output a non context diff change entry:
- * fileA[astart..aend] changed to fileB[bstart..bend]
- */
- change(astart, aend, bstart, bend)
- int astart;
- int aend;
- int bstart;
- int bend;
- {
- char c;
- /*
- * This catches a "dummy" last entry
- */
- if (astart > aend && bstart > bend)
- return;
- c = (astart > aend) ? 'a' : (bstart > bend) ? 'd' : 'c';
- if (c == 'a')
- range(astart-1, astart-1, 0); /* Addition: just print one odd # */
- else
- range(astart, aend, 0); /* Print both, if different */
- putchar(c);
- if (!eflag) {
- if (c == 'd')
- range(bstart-1, bstart-1, 1); /* Deletion: just print one odd # */
- else
- range(bstart, bend, 1); /* Print both, if different */
- }
- putchar('\n');
- if (c != 'a') {
- fetch(oldseek, astart, aend, 0, 0, lenA, infd[0], "< ");
- if (astart <= aend && bstart <= bend)
- printf("---\n");
- }
- if (c != 'd')
- fetch(newseek, bstart, bend, 0, 0, lenB, infd[1], eflag ? "" : "> ");
- if (eflag && bstart <= bend)
- printf(".\n");
- }
-
-
- /*
- * Output a context diff change entry:
- * fileA[astart..aend] changed to fileB[bstart..bend]
- */
- cchange(astart, aend, bstart, bend)
- int astart;
- int aend;
- int bstart;
- int bend;
- {
- char c;
-
- /*
- * This catches a "dummy" last entry
- */
- if (astart > aend && bstart > bend)
- return;
- c = (astart > aend) ? 'a' : (bstart > bend) ? 'd' : 'c';
- fputs("***************\n*** ", stdout);
- range(astart, aend, 0);
- fputs(" ****\n", stdout);
- fetch(oldseek, astart, aend, astart - cflag, aend + cflag, lenA, infd[0],
- c=='d' ? "- " : "! ");
- fputs("--- ", stdout);
- range(bstart, bend, 1);
- fputs(" ----\n", stdout);
- fetch(newseek, bstart, bend, bstart - cflag, bend + cflag, lenB, infd[1],
- c=='a' ? "+ " : "! ");
- }
-
- range(from, to, w)
- int from;
- int to;
- int w;
- /*
- * Print a range
- */
- {
- if (cflag) {
- if((from -= cflag) <= 0) from = 1;
- if((to += cflag) > len[w]) to = len[w];
- if(!to) from = 0;
- }
- if (to > from) {
- printf("%d,%d", from, to);
- } else if (to < from) {
- printf("%d,%d", to, from);
- } else {
- printf("%d", from);
- }
- }
-
-
- fetch(seekvec, start, end, low, high, trueend, fd, pfx)
- long *seekvec;
- register int start;
- register int end;
- int low;
- int high;
- int trueend;
- FILE *fd;
- char *pfx;
- /*
- * Print the appropriate text
- */
- {
- register int i;
- register int first;
- register int last;
-
- if (cflag) {
- if((first = low) <= 0) first = 1;
- if((last = high) > trueend) last = trueend;
- } else {
- first = start;
- last = end;
- }
- if (first > last)
- return;
- if (fseek(fd, seekvec[first], 0) != 0) {
- printf("?Can't read line %d at %08lx (hex) in file%c\n",
- start, seekvec[first],
- (fd == infd[0]) ? 'A' : 'B');
- }
- else {
- for (i = first; i <= last; i++) {
- if (fgetss(text, sizeof text, fd) == NULL) {
- printf("** Unexpected end of file\n");
- break;
- }
- #ifdef DEBUG
- printf("%5d: %s%s\n", i, pfx, text);
- #else
- fputs((cflag && (i<start || i>end)) ? " " : pfx, stdout);
- fputs(text, stdout);
- putchar('\n');
- #endif
- }
- }
- }
-
- /*
- * Input routine, read one line to buffer[], return TRUE on eof, else FALSE.
- * The terminating newline is always removed. If "-b" was given, trailing
- * whitespace (blanks and tabs) are removed and strings of blanks and
- * tabs are replaced by a single blank. Getline() does all hacking for
- * redirected input files.
- */
- int
- getline(fd, buffer)
- FILE *fd;
- char *buffer;
- {
- register char *top;
- register char *fromp;
- register char c;
-
- if (fgetss(buffer, sizeof text, fd) == NULL) {
- *buffer = EOS;
- return(TRUE);
- }
- if (fd == stdin) {
- fputs(buffer, tempfd);
- putc('\n', tempfd);
- }
- if (bflag || iflag) {
- top = buffer;
- fromp = buffer;
- while ((c = *fromp++) != EOS) {
- if (bflag && (c == ' ' || c == '\t')) {
- c = ' ';
- while (*fromp == ' ' || *fromp == '\t')
- fromp++;
- }
- if (iflag)
- c = tolower(c);
- *top++ = c;
- }
- if (bflag && top[-1] == ' ')
- top--;
- *top = EOS;
- }
- return(FALSE);
- }
- static unsigned short crc16a[] = {
- 0000000, 0140301, 0140601, 0000500,
- 0141401, 0001700, 0001200, 0141101,
- 0143001, 0003300, 0003600, 0143501,
- 0002400, 0142701, 0142201, 0002100,
- };
- static unsigned short crc16b[] = {
- 0000000, 0146001, 0154001, 0012000,
- 0170001, 0036000, 0024000, 0162001,
- 0120001, 0066000, 0074000, 0132001,
- 0050000, 0116001, 0104001, 0043000,
- };
-
- unsigned short
- hash(buffer)
- char *buffer;
- /*
- * Return the CRC16 hash code for the buffer
- * Algorithm from Stu Wecker (Digital memo 130-959-002-00).
- */
- {
- register unsigned short crc;
- register char *tp;
- register short temp;
-
- crc = 0;
- for (tp = buffer; *tp != EOS;) {
- temp = *tp++ ^ crc; /* XOR crc with new char */
- crc = (crc >> 8)
- ^ crc16a[(temp & 0017)]
- ^ crc16b[(temp & 0360) >> 4];
- }
- #ifdef DEBUG_ALL
- printf("%06o: %s\n", (crc == 0) ? 1 : crc, buffer);
- #endif
- return((crc == 0) ? (unsigned short) 1 : crc);
- }
-
-
- #ifdef vms
- opendir(which, arg, okfd)
- int which; /* Which file to open (0 or 1) */
- char **arg; /* File name argument, &argv[which] */
- FILE *okfd; /* File name (already open) */
- {
- register char *tp;
- register int c;
- register char *newname;
-
- fgetname(okfd, text);
- /*
- * Skip over device name
- */
- for (tp = text; (c = *tp) && c != ':'; tp++);
- if (c) tp++;
- else tp = text;
- /*
- * Skip over [UIC] or [PPN] if present
- */
- if (*tp == '[' || *tp == '(') {
- while ((c = *tp++) && c != ']' && c != ')');
- if (c == 0) {
- fprintf(stderr, "?Bug: bad file name \"%s\"\n",
- text);
- tp--;
- }
- }
- strcpy(text, tp);
- /*
- * Don't include version
- */
- for (tp = text; (c = *tp) && c != ';'; tp++);
- *tp = 0;
- /*
- * Now, text has the file name, tp - text, its length,
- * and *arg the (possible) directory name. Create a new
- * file name for opening.
- */
- #ifndef OSK
- if ((newname = malloc(tp - text + strlen(*arg) + 1)) == NULL)
- error("Out of space at start");
- #else
- newname = myalloc(tp - text + strlen(*arg) + 1, "Out of space at start");
- #endif
- concat(newname, *arg, text, NULL);
- if ((infd[which] = fopen(newname, "r")) == NULL)
- cant(*arg, "constructed input", 1);
- else
- *arg = newname;
- }
- #endif
-
- char *
- myalloc(amount, why)
- int amount;
- char *why;
- /*
- * Allocate or crash.
- */
- {
- register char *pointer;
-
- #ifdef OSK
- amount += sizeof(int);
- #endif
- if ((pointer = malloc((unsigned) amount)) == NULL)
- noroom(why);
- #ifdef OSK
- *((int *)pointer) = amount;
- pointer += sizeof(int);
- #ifdef DEBUG
- fprintf(stderr, "Myalloc: %d at %06o\n", amount, pointer);
- #endif
- #endif
-
- return (pointer);
- }
-
-
- /*
- * Reallocate pointer, compacting storage
- *
- * The "compacting storage" part is probably not relevant any more.
- * There used to be horrid code here that malloc'd one byte and freed
- * it at magic times, to cause garbage collection of the freespace
- * or something. It's safely gone now, you didn't have to see it.
- * -- John Gilmore, Nebula Consultants, Sept 26, 1986
- */
- char *
- compact(pointer, new_amount, why)
- char *pointer;
- int new_amount;
- char *why;
- {
- register char *new_pointer;
-
- #ifndef OSK
- #ifdef TURBO
- extern void *realloc();
- #else
- extern char *realloc();
- #endif
-
- if ((new_pointer = realloc(pointer, (unsigned) new_amount)) == NULL){
- noroom(why);
- }
- #else
- register int old_amount;
- new_amount += sizeof(int);
- if((new_pointer = malloc(new_amount)) == NULL) noroom(why);
- *(int *)new_pointer = new_amount;
- new_pointer += sizeof(int);
- old_amount = *(((int *)pointer)-1);
- /* _strass is like bcopy with the first two arguments reversted */
- _strass(new_pointer, pointer, (new_amount <= old_amount ?
- new_amount : old_amount) - sizeof(int));
- #ifdef DEBUG
- fprintf(stderr, "compact %d to %d from %06o to %06o\n",
- old_amount, new_amount, pointer, new_pointer);
- #endif
- free(pointer - sizeof(int));
- #endif
-
- #ifndef OSK
- #ifdef DEBUG
- if (new_pointer != pointer) {
- fprintf(stderr, "moved from %06o to %06o\n",
- pointer, new_pointer);
- }
- /* rdump(new_pointer, why);
- */
- #endif
- #endif
- return (new_pointer);
- }
-
- noroom(why)
- char *why;
- {
- fprintf(stderr, "?DIFF-F-out of room when %s\n", why);
- exit(IO_ERROR);
- }
-
- #ifdef DEBUG
- rdump(pointer, why)
- int *pointer;
- char *why;
- /*
- * Dump memory block
- */
- {
- int *last;
- int count;
-
- last = ((int **)pointer)[-1];
- fprintf(stderr, "dump %s of %06o -> %06o, %d words",
- why, pointer, last, last - pointer);
- last = (int *)(((int) last) & ~1);
- for (count = 0; pointer < last; ++count) {
- if ((count & 07) == 0) {
- fprintf(stderr, "\n%06o", pointer);
- }
- fprintf(stderr, "\t%06o", *pointer);
- pointer++;
- }
- fprintf(stderr, "\n");
- }
- #endif
- cant(filename, what, fatalflag)
- char *filename;
- char *what;
- int fatalflag;
- /*
- * Can't open file message
- */
- {
- fprintf(stderr, "Can't open %s file \"%s\": ", what, filename);
- #ifndef OSK
- perror((char *)NULL);
- #else
- prerr(0, errno);
- #endif
- if (fatalflag) {
- exit(fatalflag);
- }
- }
- #ifdef DEBUG
- dump(d_linep, d_len, d_which)
- LINE *d_linep;
- {
- register int i;
-
- printf("Dump of file%c, %d elements\n", "AB"[d_which], d_len);
- printf("linep @ %06o\n", d_linep);
- for (i = 0; i <= d_len; i++) {
- printf("%3d %6d %06o\n", i,
- d_linep[i].serial, d_linep[i].hash);
- }
- }
-
- dumpklist(kmax, why)
- int kmax;
- char *why;
- /*
- * Dump klist
- */
- {
- register int i;
- register CANDIDATE *cp;
- register int count;
-
- printf("\nklist[0..%d] %s, clength = %d\n", kmax, why, clength);
- for (i = 0; i <= kmax; i++) {
- cp = &clist[klist[i]];
- printf("%2d %2d", i, klist[i]);
- if (cp >= &clist[0] && cp < &clist[clength])
- printf(" (%2d %2d -> %2d)\n", cp->a, cp->b, cp->link);
- else if (klist[i] == -1)
- printf(" End of chain\n");
- else printf(" illegal klist element\n");
- }
- for (i = 0; i <= kmax; i++) {
- count = -1;
- for (cp = (CANDIDATE *)klist[i]; cp > &clist[0];
- cp = (CANDIDATE *)&cp->link) {
- if (++count >= 6) {
- printf("\n ");
- count = 0;
- }
- printf(" (%2d: %2d,%2d -> %d)",
- cp-clist, cp->a, cp->b, cp->link);
- }
- printf("\n");
- }
- printf("*\n");
- }
- #endif
- #ifdef TIMING
- ptime(why)
- char *why;
- /*
- * Dump time buffer
- */
- {
- long ttemp;
-
- ttemp = time(NULL);
- printf("%ld seconds for %s\n",
- ttemp - sectiontime, why);
- sectiontime = ttemp;
- }
- #endif
-
- /*
- * s t r e q . c
- */
-
- /*)LIBRARY
- */
-
- #ifdef DOCUMENTATION
-
- title streq String Equality Test
- index String equality test
-
- synopsis
- .s.nf
- streq(a, b);
- char *a;
- char *b;
- .s.f
- Description
-
- Return TRUE if the strings are equal.
-
- Bugs
-
- #endif
-
- /* #define EOS 0
- #define FALSE 0
- #define TRUE 1
- */
- int
- streq(s1, s2)
- register char *s1;
- register char *s2;
- /*
- * TRUE if strings are identical
- */
- {
- while (*s1++ == *s2) {
- if (*s2++ == EOS)
- return (TRUE);
- }
- return (FALSE);
- }
- /*
- * e r r o r . c
- */
-
- /*)LIBRARY
- */
-
- #ifdef DOCUMENTATION
-
- title error Fatal Error Exit
- index Fatal error exit
-
- synopsis
- .s.nf
- _error()
-
- error(format, args)
- char *format;
- .s.f
- documentation
-
- Fatal error exits. _error() halts, error() prints something
- on stderr and then halts.
-
- bugs
-
- Not a real vararg function. Only handles up to a fixed number of args.
-
- #endif
-
- /* VARARGS */
- error(format, arg1, arg2)
- char *format;
- int arg1, arg2;
- /*
- * Error message before retiring.
- */
- {
- fprintf(stderr, format, arg1, arg2);
- putc('\n', stderr);
- _error();
- }
-
- _error()
- {
- exit(1);
- }
-
- /*
- * Fgetss() is like fgets() except that the terminating newline
- * is removed.
- */
- char *fgetss(s, n, iop)
- char *s;
- FILE *iop;
- {
- int len;
-
- s[n - 1] = 0;
- if(fgets(s, n-1, iop) == NULL)
- return(NULL);
- len = strlen(s);
- if(s[len - 1] == '\n')
- s[len - 1] = 0;
- return(s);
- }
-